import java.util.ArrayList;
import java.util.List;
//子集的第一种结果：叶子结点收集
public class SubsetTest {
    //设计全局变量
    static List<Integer> path;//用来临时接受一次自己的情况
    static List<List<Integer>> ret;//用来接收全部子集情况

    //nums：表示需要计算子集的数组
    //deep：表示第几层，也是表示nums数组的第几个元素，有两种选择，选还是不选
    public static void permute(int[] nums, int deep) {
        //1.初始化
        path = new ArrayList<>();
        ret = new ArrayList<>();
        //2.开始进行回溯算法
        dfs(nums, deep);
    }

    public static void output() {
        ret.add(new ArrayList<>(path));
    }

    public static void dfs(int[] nums, int deep) {
        //递归出口
        if (deep == nums.length) {
            output();
            return;
        } else {//这回溯的核心写成决策树，是一颗二叉树，因为有两种选择
            //（1）选
            path.add(nums[deep]);
            //进入下一层
            dfs(nums, deep + 1);
            //恢复现场：移除最后一个元素
            path.remove(path.size() - 1);

            //（2）不选，因为不选没有改变path集合，所以不需要恢复现场
            dfs(nums, deep + 1);
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        permute(nums, 0);
        for (int i = 0; i < ret.size(); i++) {
            System.out.println(ret.get(i));
        }
    }
}
